package com.algorithm.cjm.interview;

/**
 * 格子路径问题
 *
 * @author jieming.chen
 * @date 2019-06-29
 */
public class PrintPath {
    int path[][] = new int[100][2];
    int m = 5, n = 2;
    // 所有路径
    int count = 0;

    // 打印路径
    void print_path(int index) {
        for (int i = 0; i < index; i++) {
            System.out.print(String.format("(%d,%d)->", path[i][0], path[i][1]));
        }
        System.out.println(String.format("(%d,%d)", m, n));
    }

    void func(int x, int y, int index) {
        path[index][0] = x;
        path[index][1] = y;
        // 终点并且打印所有路径
        if (x == m && y == n) {
            count++;
            print_path(index);
            return;
        } else if (x > m || y > n) {
            // 坐标越界退出，走另外一步
            return;
        }
        // 向右走
        func(x + 1, y, index + 1);
        // 向上走
        func(x, y + 1, index + 1);
    }

    public static void main(String[] args) {
        PrintPath printPath = new PrintPath();
//        int solve_cube_work = printPath.solve_cube_work(2, 2);
//        System.out.println(solve_cube_work);

        printPath.func(0, 0, 0);
        System.out.println(printPath.count);
    }

    int solve_cube_work(int m,int n){
        if(m==0 && n==0) {
            return 0;
        }
        if(m==1 && n==0) {
            return 1;
        }
        if(m==0 && n==1) {
            return 1;
        }
        if(m==0) {
            return solve_cube_work(m,n-1);
        }
        if(n==0) {
            return solve_cube_work(m-1,n);
        }
        return solve_cube_work(m-1,n)+solve_cube_work(m,n-1);
    }
}
